# 重排链表：https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/
# 虾皮面试题：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """ 
            核心思想，单链表不能寻找上一节点。 按照题目中的，n, n-1, n-2 的插入。 首先
            1. 找到要重新插入的第一个位置： 下标从1开始，有规律：  count // 2 + 1 的下一个节点， count是总数
            2. 将这个位置及这个位置后的这部分链表翻转
            3. 剩下的过程就很清晰了。 将 原链表的的每一个后面 插入一个 翻转后的链表节点，直到全部插入完

            插入节点时需要注意： 
            1. 节点之间的插入，需要两个指针。不注意的话，可能丢失后续节点。 
            2. 也需要注意，链表的指针是否清理干净， 需要及时置 None， 避免死循环
        """
        def reverse(node):
            """ 翻转链表 """
            head_stop = ListNode()
            while node:
                p = node
                node = node.next
                # 如果链表不为空，要先处理 node.next
                if head_stop.next:
                    print(head_stop.next.val)
                    p.next = head_stop.next
                else:
                    p.next = None
                head_stop.next = p
            return head_stop
        
        count = 0; cur = head
        # 计算链表长度, 且循环达到尾部
        while cur:
            count += 1
            cur = cur.next

        # 停止节点的位置上，在原链表中第几个（下标从1开始，也就是该节点后的节点 被重新插入）
        stop = count // 2 + 1

        # 找到需要重插的第一个节点
        cur = head
        while stop > 1: 
            cur = cur.next
            stop -= 1
        
        cur1 = cur; cur = cur.next; cur1.next = None

        # 翻转之后的节点：头插法创建单链表
        head_stop = reverse(cur)

        # 依次插入
        cur = head
        while head_stop.next:
            p = cur
            cur = cur.next

            q = head_stop.next
            head_stop.next = head_stop.next.next

            q.next = p.next
            p.next = q


# 官方解答，一样的逆序思路，但是有些地方更加精明
class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return
        
        mid = self.middleNode(head)
        l1 = head
        l2 = mid.next
        mid.next = None # 必须要断开这里
        l2 = self.reverseList(l2)
        self.mergeList(l1, l2)

    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            nextTemp = curr.next
            curr.next = prev
            prev = curr
            curr = nextTemp
        return prev

    def mergeList(self, l1: ListNode, l2: ListNode):
        while l1 and l2:
            l1_tmp = l1.next
            l2_tmp = l2.next

            l1.next = l2
            l1 = l1_tmp

            l2.next = l1
            l2 = l2_tmp        


head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

s = Solution()
s.reorderList(head)